package developer.排序算法.快速排序;

import java.util.Arrays;

/**
 * @author zhangyongkang
 * @time 2025/7/7 20:12
 * @description
 */
public class QuickSortSelf {
    /*选中一个基准 在区间中进行替换未知 确保左区间的数据比我小  右区间的数据比我大
    随后一直压缩区间 直至区间的数据为一个
     * */

    public static void main(String[] args) {
        int[] arr = {99, 55, 2, 3, 9, 10, 22, 34, 67, 89, 69, 92, 101, 102};
        sort3(arr, 0, arr.length - 1);
        Arrays.stream(arr).forEach(System.out::println);
    }


    public static void sort3(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[left];
        int start = left;
        int end = right;

        while (left < right) {
            //从右边开始
            if (arr[right] > pivot) {
                right--;
                continue;
            } else {
                arr[left] = arr[right];
                left++;
            }

            while (left < right) {
                if (arr[left] < pivot) {
                    left++;
                    continue;
                } else {
                    arr[right] = arr[left];
                    right--;
                    break;
                }
            }
        }

        //pivot index
        arr[left] = pivot;
        sort3(arr, start, left - 1);
        sort3(arr, left + 1, end);


    }


    public static void sort(int[] arr, int left, int right) {
        //快速排序,left的idx 一定是 < right 的idx
        if (left >= right) {
            return;
        }
        //选择基准点
        int pivot = arr[left];
        int begin = left;
        int end = right;
        while (left < right) {
            //从右边为起点
            if (arr[right] > pivot) {
                right--;
                continue;
            } else {//如果右侧的值大于基准  则进行数据交换
                arr[left] = arr[right];
                left++;
            }
            //从左边开始
            while (left < right) {
                if (arr[left] < pivot) {
                    left++;
                } else {
                    arr[right] = arr[left];
                    right--;
                    break;
                }
            }

        }

        arr[left] = pivot;
        sort(arr, begin, left - 1);
        sort(arr, left + 1, end);
    }
}
